import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:DELL
 * Date:2024-11-11
 * Time:22:59
 */
public class TestHeap {
    private int[] elem;//定义一个数组
    private int usedSize;//计算数组的大小

    public TestHeap() {
        this.elem = new int[10];//初始化给10个元素
    }
    //也可以从外面引入一个数组来初始化
    public void initHeap(int[] array){
        for(int i=0;i<array.length;i++){
            elem[i]=array[i];
            usedSize++;
        }
    }
    //建大堆
    public void createHeap(){
        for (int parent=(usedSize-1-1)/2;parent>=0;parent--){
            //向下调整
            shiftDown(parent,usedSize);
        }
    }
    //向下调整
    public void shiftDown(int parent,int usedSize){
        int child=(2*parent)+1;
        while (child<usedSize){
            if(child+1<usedSize&&elem[child]<elem[child+1]){
                child++;
            }
            //此时的child一定是左右孩子的最大值
            if(elem[child]>elem[parent]){
                swap(child,parent);
                parent=child;
                child=(2*parent)+1;
            }else {
                break;
            }
        }
    }
    public void swap(int child,int parent){
        int tmp=elem[child];
        elem[child]=elem[parent];
        elem[parent]=tmp;
    }
    //堆的插入
    public void offer(int val){
        if(isFull()){
            this.elem= Arrays.copyOf(this.elem,2*this.elem.length);
        }
        this.elem[usedSize]=val;
        shiftUp(usedSize);
        usedSize++;
    }
    //判满
    public boolean isFull(){
        return usedSize==elem.length;
    }
    //向上建堆
    public void shiftUp(int child){
        int parent=(child-1)/2;
        while (child>0){
            if(elem[child]>elem[parent]){
                swap(child,parent);
                child=parent;
                parent=(child-1)/2;
            }else {
                break;
            }
        }
    }
    //堆的删除---删除的是堆顶元素
    // 1.交换堆顶的元素和最后一个元素
    //2.向下建堆
    public int poll(){
        int tmp=elem[0];//记录堆顶元素
        swap(0,usedSize-1);
        shiftDown(0,usedSize-1);
        return tmp;
    }

    //堆排序
    public void heapSort(){
        int end=usedSize-1;
        while (end>0){
            swap(0,end);
            shiftDown(0,end);
            end--;
        }
    }

}
